﻿#ifndef C_ALGORITHM_LINUX_LIST_H
#define C_ALGORITHM_LINUX_LIST_H

// 这是linux 内核双向循环链表的实现形式
// 虽然名称list_head，但是它既是双向链表的表头，也代表双向链表的节点。
typedef struct list_head {
  struct list_head *prev;
  struct list_head *next;
} list_head;

// LIST_HEAD_INIT的作用是初始化节点：设置name节点的前继节点和后继节点都是指向name本身。
#define LIST_HEAD_INIT(name)                                                   \
  { &(name), &(name) }

// LIST_HEAD的作用是定义表头(节点)：新建双向链表表头name，并设置name的前继节点和后继节点都是指向name本身。
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

// INIT_LIST_HEAD和LIST_HEAD_INIT一样，是初始化节点：将list节点的前继节点和后继节点都是指向list本身。
static inline void INIT_LIST_HEAD(struct list_head *list) {
  list->next = list;
  list->prev = list;
}

// __list_add(new, prev,
// next)的作用是添加节点：将new插入到prev和next之间。在linux中，以"__"开头的函数意味着是内核的内部接口，外部不应该调用该接口。
static inline void __list_add(struct list_head *new, struct list_head *prev,
                              struct list_head *next) {
  next->prev = new;
  new->next = next;
  new->prev = prev;
  prev->next = new;
}

// list_add(new,
// head)的作用是添加new节点：将new添加到head之后，是new称为head的后继节点。
static inline void list_add(struct list_head *new, struct list_head *head) {
  __list_add(new, head, head->next);
}

// list_add_tail(new,
// head)的作用是添加new节点：将new添加到head之前，即将new添加到双链表的末尾。
static inline void list_add_tail(struct list_head *new,
                                 struct list_head *head) {
  __list_add(new, head->prev, head);
}

// __list_del(prev, next) 和__list_del_entry(entry)都是linux内核的内部接口。
static inline void __list_del(struct list_head *prev, struct list_head *next) {
  next->prev = prev;
  prev->next = next;
}

// __list_del(prev, next) 的作用是从双链表中删除prev和next之间的节点。
static inline void list_del(struct list_head *entry) {
  __list_del(entry->prev, entry->next);
}

// __list_del_entry(entry) 的作用是从双链表中删除entry节点。
static inline void __list_del_entry(struct list_head *entry) {
  __list_del(entry->prev, entry->next);
}

// list_del_init(entry)
// 的作用是从双链表中删除entry节点，并将entry节点的前继节点和后继节点都指向entry本身。
static inline void list_del_init(struct list_head *entry) {
  __list_del_entry(entry);
  INIT_LIST_HEAD(entry);
}

// list_replace(old, new)的作用是用new节点替换old节点。
static inline void list_replace(struct list_head *old, struct list_head *new) {
  new->next = old->next;
  new->next->prev = new;
  new->prev = old->prev;
  new->prev->next = new;
}

// list_entry(ptr, type, member) 实际上是调用的container_of宏。
// 它的作用是：根据"结构体(type)变量"中的"域成员变量(member)的指针(ptr)"来获取指向整个结构体变量的指针。
#define list_entry_lnx(ptr, type, member) container_of_lnx(ptr, type, member)

// list_for_each(pos, head)和list_for_each_safe(pos, n,
// head)的作用都是遍历链表。但是它们的用途不一样！

// list_for_each(pos, head)通常用于获取节点，而不能用到删除节点的场景。
#define list_for_each(pos, head)                                               \
  for (pos = (head)->next; pos != (head); pos = pos->next)

// list_for_each_safe(pos, n, head)通常删除节点的场景。
#define list_for_each_safe(pos, n, head)                                       \
  for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)

// offsetof在linux内核的include/linux/stddef.h中定义。

// 说明：获得结构体(TYPE)的变量成员(MEMBER)在此结构体中的偏移量。
// (01)  ( (TYPE *)0 )   将零转型为TYPE类型指针，即TYPE类型的指针的地址是0。
// (02)  ((TYPE *)0)->MEMBER     访问结构中的数据成员。
// (03)  &( ( (TYPE *)0 )->MEMBER )
// 取出数据成员的地址。由于TYPE的地址是0，这里获取到的地址就是相对MEMBER在TYPE中的偏移。
// (04)  (size_t)(&(((TYPE*)0)->MEMBER))
// 结果转换类型。对于32位系统而言，size_t是unsigned
// int类型；对于64位系统而言，size_t是unsigned long类型。 #define offsetof(TYPE,
// MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define offsetof_lnx(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER)

// container_of在linux内核的include/linux/kernel.h中定义。

// 说明：根据"结构体(type)变量"中的"域成员变量(member)的指针(ptr)"来获取指向整个结构体变量的指针。
// (01) typeof( ( (type *)0)->member )     取出member成员的变量类型。
// (02) const typeof( ((type *)0)->member ) *__mptr = (ptr)
// 定义变量__mptr指针，并将ptr赋值给__mptr。经过这一步，__mptr为member数据类型的常量指针，其指向ptr所指向的地址。
// (04) (char *)__mptr    将__mptr转换为字节型指针。
// (05) offsetof(type,member)) 就是获取"member成员"在"结构体type"中的位置偏移。
// (06) (char *)__mptr - offsetof(type,member))
// 就是用来获取"结构体type"的指针的起始地址（为char *型指针）。 (07) (type *)(
// (char *)__mptr - offsetof(type,member) )    就是将"char
// *类型的结构体type的指针"转换为"type *类型的结构体type的指针"。

#define container_of_lnx(ptr, type, member)                                    \
  ({                                                                           \
    const typeof(((type *)0)->member)(*mbr_ptr) = (ptr);                       \
    (type *)((char *)mbr_ptr - offsetof_lnx(type, member));                    \
  })

// list_empty(head)的作用是判断双链表是否为空。它是通过区分"表头的后继节点"是不是"表头本身"来进行判断的。
static inline int list_empty(const struct list_head *head) {
  return head->next == head;
}

#endif